1. Field of the Invention
This invention relates to the field of communication and data storage systems, and in particular to the decoding of communications that contain block-based error correction codes.
2. Description of Related Art
One of the parameters used to specify the quality of a digital communication system is the xe2x80x9cBit Error Ratioxe2x80x9d, or BER. The BER specifies the probability that an erroneous bit is produced at the output of the receiving system. Specifications for storage devices (tapes, disk, CD, DVD, barcode), mobile communications (cellular telephone, microwave links), satellite communications, digital television, and the like, often require BERs in the order of 10xe2x88x929 or less. One technique for providing a low probability of error is to transmit the information using a high powered transmitter to achieve a high signal to noise ratio (SNR). This is often impractical or costly, particularly for mobile systems that use batteries to supply the transmit power, and broadcast systems that must conform to interference standards, such as published by the FCC.
An alternative method of achieving a high BER without relying on a high SNR is to encode the information with an error correcting code, so that when an error occurs during a transmission, it can be corrected by the receiver, and therefore will no longer be an xe2x80x9cerrorxe2x80x9d. Error correcting techniques are commonly available for automatically correcting multiple errors within a transmission.
A commonly used error correcting technique is a Reed-Solomon error correcting code. Using Reed-Solomon (R-S) terminology, fixed-length (n) codewords are transmitted, each codeword comprising k information symbols and nxe2x88x92k appended error correcting parity symbols. Each symbol comprises s bits. A R-S decoder can correct up to (nxe2x88x92k)/2 symbols that contain errors in a codeword. Because each of these correctable symbols may contain multiple bit-errors, the R-S encoding technique is particularly well suited for burst errors that affect multiple contiguous bits. A common R-S encoding scheme uses a codeword of 255 eight-bit symbols, 223 of which are information symbols, and the remaining 32 symbols are error correcting parity symbols. This encoding scheme will correct up to 16 erroneous symbols in every 255 codeword, thereby providing a substantial improvement in Bit Error Rate.
The R-S encoding scheme will also detect xe2x80x9cerasuresxe2x80x9d, which are errors at known locations, and require less information to correct. The number of errors plus twice the number of erasures that an R-S decoder can correct is (nxe2x88x92k)/2. For ease of reference, the term xe2x80x9cerrorxe2x80x9d is used hereinafter to refer to either an error of unknown location or an erasure of known location.
FIG. 1 illustrates an example block diagram of a prior art R-S decoder 100. The decoder 100 receives each codeword r(x) 101, and produces a corrected codeword c(x) 151. A syndrome calculator 110 processes the codeword 101 to produce corresponding syndrome polynomials Si(x) 111. Each codeword has nxe2x88x92k syndromes that depend only on errors, and not on the transmitted codeword. From these syndromes 111, an error locator polynomial xcex9(x) 121 is produced. Euclid""s algorithm 120 is illustrated for providing the error locator polynomial 121, and an error magnitude polynomial xcexa9(x) 122, although other techniques, such as the Berlekamp-Massey algorithm can be used as well. Each R-S code has a parameter a that is the primitive element of a Galois Field (GF) that is chosen for the R-S code. The error locator polynomial is structured such that if an error occurs at position p, axe2x88x92p will be a root of the error polynomial (p is indexed from 0 to nxe2x88x921).
An iterative approach is conventionally applied to test each value of axe2x88x92p for each position p in the codeword, to determine if axe2x88x92p is a root, Xkxe2x88x921, of the error locator polynomial 121. A commonly used algorithm for this iterative test is the Chien error locator 130. The Chien locator 130 also provides a related error differential term, Xkxe2x88x921xcex9xe2x80x2(Xkxe2x88x921) 132, that facilitates a determination of the magnitude 141 of the error, typically via the Forney error determination algorithm, as illustrated at block 140. The error determinator 140 evaluates the error magnitude polynomial 122 corresponding to the located error symbol. For each error that the error locator 130 locates, an error corrector 150 determines the corrected codeword c(x) 151, based on the location 131 and magnitude 141 of this error. If an error is not detected for a given symbol, the symbol in the corrected codeword c(x) 151 at this evaluated position is equal to the symbol in the received codeword r(x) 101.
FIG. 2 illustrates an example block diagram of a prior art Chien error locator 130. The error locator 130 includes a plurality of polynomial term evaluators 220. Each evaluator 220 includes a register 221 and a coefficient multiplier 225. The set of registers 221 receive the coefficients xcex of the error locator polynomial xcex9(x) 121, and the set of coefficient multipliers 225 multiply the coefficients xcex by corresponding powers of a 222 and store the resultant product terms into the registers 221. With regard to the output polynomial value 231, the adders 230a, 230b, and 230c form a single adder that combines the product terms of each coefficient multiplier 225. That is, initially the adders provide the sum of the coefficients xcex, corresponding to an evaluation of the error locator polynomial xcex9(x) 121 at a0 (i.e. value=xcexnxe2x88x921(a0)nxe2x88x921+xcexnxe2x88x922(a0)nxe2x88x922+ . . . +xcex2(a0)2+xcex1(a0)1+(a0)0xcex0). If this value 231 is zero, a0 is a root, indicating that an error is present at position 0. In like manner, after multiplying the powers of a 222 with the corresponding coefficients xcex of the error locator polynomial xcex9(x) 121, the polynomial value 231 is the evaluation of the error locator polynomial xcex9(x) 121 at axe2x88x921 (i.e. value=xcexnxe2x88x921(axe2x88x921)nxe2x88x921+xcexnxe2x88x922+ . . . +xcex2(axe2x88x921)2+xcex1(axe2x88x921)1+(axe2x88x921)0xcex0). If this value 231 is zero, axe2x88x921 is a root, indicating that an error is present at position 1. At the next cycle, the contents of the registers 221 are again multiplied by powers of a 222. This results in a squaring of each power of a 222, and the polynomial value 231 corresponds to the evaluation of the error locator polynomial at axe2x88x922 (i.e. value=xcexnxe2x88x921(axe2x88x922)nxe2x88x921+xcexnxe2x88x922(axe2x88x922)nxe2x88x922+ . . . +xcex2(axe2x88x922)2+xcex1(axe2x88x922)1+xcex0(axe2x88x922)0). If this value 231 is zero, axe2x88x922 is a root, indicating that an error is present at position 2. The next cycles correspond to an evaluation of the polynomial at axe2x88x923, then axe2x88x924, then axe2x88x925, and so on. The iterative process continues until all n symbol positions (0 to nxe2x88x921) are evaluated. As noted above, the conventional Chien locator 130 also provides a derivative term Xkxe2x88x921xcex9xe2x80x2(Xkxe2x88x921) 132 that facilitates the determination of the error magnitude 141 in the error determinator 140 corresponding to a located root Xkxe2x88x921 of the locator polynomial xcex9(x). The derivative term 132 is illustrated in FIG. 2 as a partial sum of the even polynomial terms; alternatively, the odd terms can be used.
To reduce the time required to evaluate all n symbols of an error correcting codeword, redundant parallel embodiments of the iterative components can be considered. That is, in principle, if two copies of the error locator 130 and error determinator 140 are provided, the odd powers of a could be evaluated by one set of locator/determinators, and the even powers of a evaluated in the other. Alternatively, one set of locator/determinators could be used to process the first half of symbols, while the other set of locator/determinators is used to process the other half, thereby facilitating the single multiplication of the powers of a 222 per cycle as in the conventional prior art device. However, the registers 221 of the set of locator/deteminators used for the xe2x80x9csecondxe2x80x9d half of the symbols would need to be initialized to the appropriate powers of a 222 times the xcex terms, which would require additional components. Each redundant set, however, requires a corresponding direct linear increase in area (two sets=twice the area; three sets=3xc3x97the area; etc.), plus any additional circuitry required to effect the partitioning of the process.
It is an object of this invention to reduce the time required to evaluate all n symbols of an error correcting codeword. It is a further object of this invention is reduce the number of components required to evaluate all n symbols of an error correcting codeword, as compared to a redundant embodiment of prior art components.
These objects and others are achieved by providing a polynomial evaluator that includes a plurality of slice elements corresponding to each term of the polynomial. Each slice element includes a plurality of coefficient multipliers that are configured to evaluate the term for different values, thereby effecting a simultaneous evaluation of the polynomial at each of these different values. In a preferred embodiment, only one register is required in each slice element for receiving the coefficients of the polynomial and for facilitating an iterative evaluation of the polynomial for other values. In a preferred embodiment, two polynomial evaluators are employed for decoding a Reed-Solomon codeword. One evaluator embodies a modified form of the Chien error locator algorithm, and the other embodies a modified form of the Forney error determination algorithm.